\section{Ejercicio 3}

Se dispone de un tablero de $n \times m$ en el que se colocan $t$ fichas, en $t$ casillas distintas. El objetivo del juego es ir
eliminando las fichas mediante saltos hasta dejar solo una.

Una ficha se saca del tablero cuando otra adyacente salta por sobre ella en sentido vertical u horizontal quedando en
el casillero inmediato siguiente, que debe estar desocupado antes del salto.

Para cada configuraci\'on de fichas ofrecidas indicar, de ser posible, los pasos a seguir para eliminar todas las fichas menos una.

\textbf{Entrada: } \texttt{Tp1Ej3.in}

El archivo contiene varias instancias, y cada una consta de dos l\'ineas. La primera contiene $n$ y $m$ separados por un blanco.
La segunda contiene una sucesi\'on de $t$ pares indicando las coordenadas $x$ e $y$ de las respectivas $t$ fichas, usando blancos 
como separadores entre $x$ e $y$, y ``;'' como separador de las coordenadas.
La secuencia ser\'a de la forma: \texttt{<x> <y>[;<x> <y>]} y donde: \texttt{<x>} e \texttt{<y>} son enteros

\textbf{Salida: } \texttt{Tp1Ej3.out}

Para cada instancia de entrada, se debe indicar una l\'inea con la serie de pasos necesarios para resolver el juego, o una
l\'inea en blanco si no es posible.

La secuencia de pasos ser\'a la forma:

\texttt{<coordenada de origen>;<coordenada de destino>[;<coordenada de origen>;<coordenada de destino>]}
Donde: \texttt{coordenada de origen: <x> <y>}

\subsection{Introducci\'on}

Para resolver el ejercicio se implement\'o un algoritmo de busqueda exhaustiva (m\'as conocido como ``backtracking''), que examina las posibles movidas.
Se incluyo tambi\'en una poda b\'asica al algoritmo, basada en un invariante del juego.

\subsection{Desarrollo}

\subsubsection{Explicaci\'on del Algoritmo}

El algoritmo implementado para resolver el problema se basa en la estructura b\'asica de b\'usqueda exhaustiva. Este m\'etodo consiste en emplear recursi\'on
para generar sucesivamente todos los posibles estados del problema. En nuestro caso, un estado del problema es la configuraci\'on del tablero en un momento dado.

El algoritmo realiza este paso simplemente probando todas las posibles transiciones v\'alidas de un estado a otro. En nuestro caso, el algoritmo intenta cada
movimiento v\'alido. De esta manera, si partiendo del estado inicial (el tablero como es dado al iniciar el algoritmo) el algoritmo encuentra un estado terminal
, un estado donde no hay posibles transiciones v\'alidas a un estado no previamente considerado, tenemos dos casos. Si este estado terminal es resoluble, lo
cual para el problema actual consiste en que quede solo una ficha en el tablero, entonces la secuencia generada de transiciones consiste en una secuencia
v\'alida de movimientos, lo cual consiste en la soluci\'on pedida por el problema. Si el estado es t\'erminal pero no ganador, no es posible ni necesario propagar m\'as
ya que no existe una transici\'on a un estado no ya visto (por la definici\'on de estado terminal).

Una observaci\'ion importante es que los estados, junto con las transiciones, forman un grafo dirigido ac\'iclico. Con esto nos referimos a que no existe una
secuencia de transiciones v\'alidas que nos lleven de un estado a si mismo. En el caso de nuestro problema, desconsiderando la terminolog\'ia, esto es obvio:
Si partimos de un tablero con $t$ fichas, en cada movimiento comemos una ficha, por lo tanto nunca podr\'ia pasar que volvieramos a considerar el estado inicial
porque esto implicar\'ia que en alg\'un paso no se comieron o se crearon fichas, lo cual por las reglas del juego es imposible.

Otra observaci\'on clave para la implementaci\'on es que toda transici\'on es reversible: deshacer un movimiento es f\'acil (ponemos una ficha donde estaba la
que comimos, y movemos la ficha que salt\'o a su lugar inicial). Tambi\'en tenemos que el problema requiere que devolvamos alguna secuencia de movimientos, no
la m\'as \'optima en alg\'un sentido.

Propusimos e implementamos entonces el siguiente algoritmo como primera versi\'on. Para detener el algoritmo cuando encuentra una soluci\'on, usamos
una variable global \texttt{termine} y guardamos en una lista enlazada \texttt{listaMovimientos} los movimientos que vamos sucesivamente probando.

\begin{algorithm}[!h] 
	\caption{Pseudoc\'odigo para probar recursivamente todas las movidas v\'alidas del juego del Ejercicio 3.}
	\label{algo::backtracking}
	\begin{algorithmic} 
		\State \Var $termine \gets $ \False
		\State \Var $movimientos \gets []$
		
		\Function{backtrack}{Juego j}
			\If{$fichasRestantes(j) == 1$}
				\State $termine \gets $ \True
			\Else
				\ForAll{$ficha \in fichas(j)$}
					\If{puede saltar alguna $vecina$}
						\State $j \gets hacerMovimiento(ficha,vecina)$
						\State $movimientos \gets movimientos \bullet (ficha \rightarrow vecina)$
						\Statex
						\State $backtrack(j)$
						\Statex
						\If{termine} 
							\State \Return 
						\EndIf
						\State $movimientos \gets quitarUltimo(movimientos)$
						\State $j \gets deshacerMovimiento(ficha,vecina)$
					\EndIf
				\EndFor
			\EndIf
		\EndFunction
	\end{algorithmic}
\end{algorithm}

Podemos ver que este algoritmo utilizando inducci\'on.

Primero probamos el siguiente lema.

\begin{lemma}
	El algoritmo \ref{algo::backtracking}, cuando llamado sobre un tablero terminal no ganador, no modifica este tablero. Tampoco modifica la lista de movimientos.
\end{lemma}

\begin{proof}
	La clave para ver esto es que un tablero terminal no resoluble siempre tiene $t \geq 2$ fichas (lo cual es evidente por la definici\'on de tablero resoluble).
	Entonces, por inducci\'on en la cantidad de fichas:
	
	\begin{itemize}
		\item $t = 2$. Puesto que el tablero no se puede resolver, no existe un movimiento que nos lleve a un estado con $t-1 = 1$ fichas. Por lo tanto,
		ninguna ficha puede comer a la otra. El ciclo \texttt{for} del algoritmo recorrera entonces todas las fichas y no encontrar\'a ningun movimiento posible,
		dejando entonces al tablero como esta. Puesto que solo se agregan elementos en el cuerpo interno del \texttt{if} del ciclo \texttt{for}, tampoco modificamos
		la lista de movimientos en este caso.
		
		\item $t \rightarrow t+1$. Si tenemos que el tablero tiene $t+1$ fichas, y no hay ningun movimiento posible donde una ficha salte a la otra, no hay
		nada que probar (porque podemos seguir un argumento an\'alogo al caso $t = 2$). En cambio, si existe un movimiento, vemos que el algoritmo lo primero
		que hace es agregar el movimiento a la lista de movimientos, y entonces realiza el movimiento. El tablero resultante tiene entonces $t-1$ fichas, 
		porque retiramos la ficha que comimos en el movimiento. Adem\'as, como el tablero es terminal no resoluble, el tablero obtenido es tambi\'en no resoluble.
 		Entonces, por hip\'otesis inductiva, despu\'es de la llamada recursiva a \texttt{backtrack}, ni el tablero ni la lista de movimientos han sido modificadas.
 		Por lo tanto, al retirar el movimiento agregado al final de la lista de movimientos, y al deshacer el movimiento realizado, volvemos el tablero al estado que ten\'ia
 		antes de iteraci\'on del ciclo. Por lo tanto, al finalizar todas las iteraciones, el tablero sigue sin modificar, como quer\'iamos demostrar. \qed
	\end{itemize} 
\end{proof}

\begin{lemma}
	El algoritmo \ref{algo::backtracking} genera todas las posibles secuencias de movimientos hasta que encuentra una
	que resuelve el juego pasado como par\'ametro, o devuelve una lista vac\'ia en caso de que sea trivial o no se pueda resolver.
\end{lemma}

\begin{proof}
	Supondremos que la variable booleana \texttt{termine} es falsa al iniciar para el juego actual, y que la lista de movimientos
	inicia vac\'ia.
	
	Por inducci\'on en la cantidad de fichas $t$ restantes.
	
	\begin{itemize}
		\item $t = 1$. Si queda una sola ficha en el tablero entonces es una movida ganadora y por lo tanto el estado es t\'erminal y ganador.
		Efectivamente, no hay que hacer ningun movimiento porque ya hemos ganado.

		Observemos tambi\'en que la variable \texttt{termine} se pone en verdadero solo en este caso. Por lo tanto, la variable \texttt{termine} es
		verdadera solo si se llega a un estado terminal resoluble (es decir, con una sola ficha).

		\item $t \rightarrow t+1$. Supongamos que tenemos un tablero con $t+1$ fichas. El algoritmo revisa entonces todos los movimientos posibles (ya
		que un movimiento v\'alido consiste en hacer saltar una ficha con una ficha v\'ecina, y el espacio a donde salta esta libre). Si encuentra un movimiento
		posible, entonces realiza el movimiento, agrega el movimiento a la lista y llama a backtracking con el nuevo juego.

		Hay dos posibles casos:
		
		\begin{itemize}
			\item El tablero obtenido es resoluble. Por lo tanto, la lista de movimientos consiste en el movimiento que reduce el tablero con $t+1$ fichas a
			un tablero resoluble con $t$ fichas, y los movimientos que resuelven este tablero de $t$ fichas. Es evidente entonces que \texttt{listaMovimientos}
			constituye una serie de movidas que resuelven el tablero pasado inicialmente por par\'ametro.
			
			Tambi\'en vemos que como el tablero es resoluble, se pone la variable $termine$ en verdadero alg\'un momento, puesto que con la secuencia de movimientos de \texttt{listaMovimientos} excepto la primera
			llegamos a un tablero terminal resoluble. Por lo tanto, al terminar al finalizar la llamada backtracking, la funci\'on termina inmediantamente, sin
			modificar el contenido de la lista. Por lo tanto, la lista \texttt{listaMovimientos} final contiene una secuencia que resuelve el tablero pasado
			por par\'ametro.
					
			\item El tablero obtenido no es resoluble. Por lo tanto, por el lema anterior la lista de movimientos y el tablero no se ven alterados. Por lo tanto,
			al deshacer la \'ultima inserci\'on en la lista y al deshacerse la movida (lo cual reduce el tablero a su estado antes de iniciar la ejecuci\'on de la
			iteraci\'on actual), tenemos el tablero original, y probamos otro movimiento.
			
			Puesto que ningun movimiento resuelve, la lista final por lo tanto sera igual a la lista al iniciar el algoritmo, es decir, vac\'ia.
		\end{itemize}
		
		Al haber probado la hip\'otesis y el paso inductivos, se tiene lo que quer\'iamos demostrar. \qed
	\end{itemize}
\end{proof}

Para acelerar el algoritmo, agregamos tambi\'en una poda, basada en el siguiente lema.

\begin{lemma}
	Coloreemos el tablero de juego como si fuese un tablero de ajedrez (es decir, alternando colores entre filas y columnas). En un tablero
	donde todas las fichas est\'an del mismo color, no existe un movimiento v\'alido.
\end{lemma}

\begin{proof}
	Es f\'acil ver este lema puesto que un movimiento consiste en que una ficha salte a otra ficha vecina. Por lo tanto, para que pueda ocurrir
	este salto, la ficha que salta y la ficha a saltar deben ser adyacentes por un lado, y por lo tanto estan en la misma columna y diferente fila
	o viceversa. Esto implica que en nuestra coloraci\'on tienen colores opuestos. Por lo tanto, si no hay fichas con colores opuestos, no hay
	fichas vecinas y realizar un movimiento es imposible.
\end{proof}

Esto entonces nos permite evitar an\'alizar algunos casos: Si antes de empezar a fijarnos un movimiento, podemos determinar que el tablero que
queremos resolver tiene todas sus fichas en casillas del mismo color, el paso no es necesario, podemos terminar inmediatamente sin probar ninguno
de los movimientos. 
El algoritmo ~\ref{algo::backtracking_posta}, junto con esta poda adicional, no se encuentra descripto en una figura aparte, puesto que consiste
solamente en adicionar el siguiente c\'odigo

\begin{algorithmic} 
	\Statex
	\If{$fichasNegras(j) == 0 || fichasBlancas(j) = totalFichas(j)$}
		\State \Return;
	\EndIf
\end{algorithmic}

antes de empezar el ciclo \texttt{for} que recorre todas las casillas. Lo que hacemos efectivamente es no continuar explorando ese tablero pues el
lema nos da un atajo que dice que no se puede resolver.

\subsubsection{Complejidad de los algoritmos}

Antes de empezar, en esta parte del an\'alisis ignorar\'emos la poda presentada para realizar nuestro an\'alisis, volveremos a ella
al final para hacer algunas aclaraciones.

Para analizar los algoritmos presentados para resolver este problema, primero calculemos la cantidad de llamadas recursivas que se realizan
al procedimiento \texttt{backtrack}. Tenemos que el algoritmo realiza una llamada recursiva de \texttt{backtrack} para cada estado del tablero
al que podemos llegar a partir de movimientos v\'alidos desde el inicial. Para acotar esta cantidad de movimientos, podemos observar lo siguiente:

\begin{lemma}
	La ``profundidad'', es decir, la cantidad de m\'axima de llamadas recursivas anidadas que hace el algoritmo~\ref{algo::backtracking}, es $t-1$,
	la cantidad de fichas del tablero.
\end{lemma}

\begin{proof}
	El algoritmo~\ref{algo::backtracking} realiza una llamada recursiva por cada movimiento posible, que consiste en una transici\'on de un tablero
	a otro, y repite esto para el tablero obtenido al realizar el movimiento, si sobre este tablero puede realizarse un movimiento. 
	Esto implica que una secuencia de movimientos es explorada en el algoritmo como una secuencia de llamadas recursivas anidadas.

	Cada movimiento posible elimina una sola ficha del tablero (puesto que saltamos una ficha). Tambi\'en, como vimos anteriormente, el algoritmo termina si llega a un tablero terminal,
	donde queda una sola ficha. Por lo tanto, como se pueden realizar como m\'aximo $t-1$ movimentos para llegar a un tablero con una sola ficha a partir
	de uno con $t$, y cada secuencia de movimientos consiste en una secuencia de llamadas recursivas anidadas,
	tenemos que la cantidad de llamadas recursivas esta acotada por $t-1$, con $t$ la cantidad de fichas del tablero. \qed
\end{proof}

Esto es equivalente a demostrar que el \'arbol de llamadas recursivas tiene una altura m\'axima de $t-1$. Cada nodo de este \'arbol representa un estado
y cada arista representa un movimiento. Como el algoritmo~\ref{eq::backtracking} explora todo este \'arbol de estados, lo que queremos es acotar la cantidad
de nodos del mismo. Tenemos una cota de la altura, y tenemos que el primer nivel tiene un solo nodo (la ra\'iz del arbol, el tablero con el cual iniciamos).
Ahora debemos calcular a cuandos nodos se propaga en cada nivel. Esto implica ver cuantos movimientos como m\'aximo es posible realizar para un tablero.

\begin{lemma}
	En un tablero de $t$ fichas, pueden realizarse como m\'aximo $2t$ movimientos.
\end{lemma}

\begin{proof}	
	\begin{figure}[ht]
		\label{fig::configs}
		\caption{Posibles configuraciones de una ficha y sus vecinas. Como podemos ver, en todos los casos la ficha azul puede ser comida en como m\'aximo
		$2$ maneras.}
		\centering
		\includegraphics[width=0.7\textwidth]{img/configs.png}
	\end{figure}

	Centremosnos en una ficha determinada. El detalle puede verse en la figura~\ref{fig::configs}.
	
	Como podemos ver en la figura, la ficha az\'ul en todos los casos puede ser comida o saltada de dos maneras por alguna de sus fichas vecinas. Dado que
	todo movimiento consiste en que una ficha salte a otra, vemos trivialmente que habiendo $t$ fichas y siendo que cada ficha solo puede ser saltada de
	dos maneras, hay $2t$ movimientos posibles como m\'aximo. 	\qed
\end{proof}

Juntando estos dos resultados, tenemos que

\begin{theorem}
	La cantidad de llamadas recursivas que realiza el algoritmo~\ref{algo::backtracking} es $O(2^{t-1} t!)$.
\end{theorem}

\begin{proof}
	Como vimos anteriormente, nuestro \'arbol de llamadas parte de un nodo inicial (el tablero que queremos resolver). Cada nodo se expande en como m\'aximo
	$2t$ otros nodos, que corresponde a los tableros a los cuales podemos llegar realizando un movimiento a partir del tablero que estamos mirando.
	Esto se puede repetir un m\'aximo de $t$ veces, y en cada nivel tenemos que los tableros tienen una ficha menos que sus tableros padres (porque cada
	movimientos consiste en extraer una ficha). Por lo tanto tenemos que la cantidad de nodos de nuestro \'arbol es
	
	\begin{align*}
		\underbrace{2t \cdot 2(t-1) \cdot \dots \cdots 2}_\textrm{$t-1$ veces} & = \underbrace{2 \cdot 2 \cdot \dots \cdots 2}_\textrm{$t-1$ veces} \cdot t(t-1)(t-2)\dots 1\\
		& = 2^{t-1} t!
	\end{align*} 
	
	como quer\'iamos demostrar \qed
\end{proof}

Por lo tanto tenemos una cota de la cantidad de llamadas recursivas de nuestro algoritmo. Por lo tanto el costo temporal total de nuestro algoritmo estar\'a
ser\'a del \'orden de $O(2^{t-1} t! c)$ con $c$ el costo (desconsiderando la llamada recursiva) de cada llamada a \texttt{backtrack}.

Para analizar el coste $c$ de nuestra implementaci\'on es necesario mirar m\'as de cerca la implementaci\'on realizada del algoritmo. Posteriormente veremos
que efectivamente la implementaci\'on es la realizada en Java.

En el algoritmo~\ref{algo::backtracing_posta} contiene m\'as detalladamente la implementaci\'on de algunas de las operaciones encapsuladas en el
algoritmo~\ref{algo::backtracking}. La implementaci\'on realizada simplemente recorre todo el tablero y por cada ficha se fija si esta es capaz
de hacer un movimiento en alguna de las 4 direcciones (Norte, Sur, Este y Oeste, si se quiere). Si efectivamente puede hacerlo, entonces prueba ese movimiento
de la manera descripta y analizada anteriormente. Lo que esto implica es que tenemos un costo $c = O(4t+mn)$ si suponemos que las operaciones de la lista y
pasaje de par\'ametros se realizan en $O(1)$ (posteriormente veremos que esto es efectivamente as\'i) y que se puede iterar sobre las casillas del juego
en $O(nm)$. El costo $mn$ viene por el hecho de que para casilla nos fijamos si tiene una ficha, y el costo $4t$ viene por el hecho de que para casilla que tiene una ficha nos fijamos las posibles casillas donde podr\'ia
haber una ficha que pudiera saltar.

Por lo tanto con esta implementaci\'on nuestro algoritmo tiene complejidad temporal $O((nm+4t)2^{t-1}t!)$.

\begin{algorithm}[!h] 
	\caption{Pseudoc\'odigo para probar recursivamente todas las movidas v\'alidas del juego del Ejercicio 3, con detalles de implementaci\'on.}
	\label{algo::backtracking_posta}
	\begin{algorithmic} 
		\State \Var $termine \gets $ \False
		\State \Var $movimientos \gets []$
		
		\Function{backtrack}{Juego j}
			\If{$fichasRestantes(j) == 1$}
				\State $termine \gets $ \True
			\Else
				\ForAll{$c \in casillas(j)$}
					\If{$hayFicha(j,c)$}
						\ForAll{$d \in direcciones$}
							\If{$c$ puede saltar una vecina $v$ en la direccion $d$}
								\State $j \gets hacerMovimiento(ficha,vecina)$
								\State $movimientos \gets movimientos \bullet (c \rightarrow v)$
								\Statex
								\State $backtrack(j)$
								\Statex
								\If{$termine$} 
									\State \Return 
								\EndIf
								\State $movimientos \gets quitarUltimo(movimientos)$
								\State $j \gets deshacerMovimiento(ficha,vecina)$
							\EndIf
						\EndFor
					\EndIf
				\EndFor
			\EndIf
		\EndFunction
	\end{algorithmic}
\end{algorithm}

Finalmente, para describir detalles de los requerimientos temporales de memoria, consideremos la implementaci\'on de las operaciones descriptas
en el algoritmo~\ref{algo::backtracking_posta}. Para implementar las operaciones $hacerMovimiento, deshacerMovimiento$ y para recorrer las casillas
en \'orden, se represent\'o explic\'itamente el tablero como una matriz booleana, donde \True representa una casilla donde hay una ficha y \False
donde no la hay. Por lo tanto, determinar (dadas las coordenadas) si una casilla tiene o no una ficha es $O(1)$, y recorrer todas las casillas es
$O(nm)$ (despu\'es veremos como esto se implementa en Java). Sin embargo, esto pone adem\'as un peso en memoria, ya que ahora requerimos $O(nm)$
booleanos, lo cual requiere $O(nm)$ puesto que el tipo \texttt{boolean} es primitivo en Java. Adicionalmente, requerimos $O(t)$ memoria por la lista
de movimientos. Esto requiere $O(t)$ memoria puesto que cada elemento de la lista consiste en un movimiento (que se puede representar como dos
casillas, que a su vez se puede representar como dos enteros primitivos de Java que ocupan $O(1)$ memoria) y la lista puede contener en cualquier momento
hasta $t$ elementos.

Una nota final sobre la poda adicionada al algoritmo. La poda efectivamente no cambia la complejidad del algoritmo presentado en~\ref{algo::backtracking_posta},
sino que simplemente nos sirve para remover algunas ramas del \'arbol de posibilidades de manera sencilla, sin embargo no lo consideramos en el c\'alculo
de complejidad. Posteriormente se verificar\'a experimentalmente si la poda efectivamente modifica el tiempo de ejecuci\'on del algoritmo.

\subsection{Detalles de la implementaci\'on en Java}

La implementaci\'on realizada es bastante fiel al pseudoc\'odigo presentado en el algoritmo~\ref{algo::backtracking_posta}. Para encapsular el comportamiento
del tablero se creo una clase \texttt{Juego}, que contiene los m\'etodos necesarios para realizar todos los pasos del algoritmo. Por ejemplo, la clase
provee de un iterador \texttt{IteradorCasilla}, similar al utilizado en la soluci\'on del ejercicio 2, que nos permite iterar sobre todas las casillas casillas
importantes del tablero. De manera similar al ejercicio anterior, el hecho de que sea una clase interna y que todas las operaciones consistan en devolver
una referencia, o hacer operaciones de asignaci\'on, comparaci\'on o aritm\'eticas sobre variables de tipos primitos de Java hace que dada una casilla
obtener la siguietne en el \'orden de iteraci\'on sea $O(1)$ y por lo tanto iterar sobre todas las casillas sea $O(nm)$.

Para obtener las vecinas de una casilla reutilizamos las clases \texttt{Posicion} y \texttt{Direccion}, utilizada en el ejercicio anterior, y proveemos
m\'etodos para determinar si una casilla esta dentro del tablero (\texttt{esCasilla}), y para determinar si hay una ficha, poner una ficha y sacar
una ficha de una casilla del tablero (\texttt{hayFicha},\texttt{agregarFicha} y \texttt{ponerFicha}. Internamente tenemos m\'etodos que manejan
las operaciones de mantener los colores de las casillas, utilizadas para implementar la poda presentada. Estas simplmente consisten en dos contadores,
inicializados y mantenidos por los m\'etodos internos de la clase, de la cantidad de fichas negras y blancas. Adicionalmente se proveen tres m\'etodos,
uno para devolver la cantidad de fichas negras en el tablero (\texttt{fichasNegras()}) otra para las blancas (\texttt{fichasBlancas()}) y uno para la
cantidad de fichas totales (\texttt{contarFichas}).

Todas estas operaciones son $O(1)$ puesto implican operaciones del comparaci\'on, asignaci\'on y aritm\'eticas sobre tipos primitivos, y pasaje de par\'ametros.
Como ya describimos, el pasaje de par\'ametros en Java es $O(1)$ puesto que los par\'ametros que son tipos primitivos son pasados como tales pero ocupan $O(1)$
memoria y por lo tanto cuesta $O(1)$ copiarlos, y los tipos no primitivos son pasados por referencia lo cual implica que simplemente pasamos un puntero al 
objeto en la heap del asignador de memoria de Java.

Por otro lado, tenemos tambi\'en que las operaciones \texttt{hacerMovimiento} y \texttt{deshacerMovimiento} son $O(1)$, puesto que consisten en utilizar
una cantidad finita de veces las operaciones para alterar si hay una ficha o no en una casilla, lo cual como ya dijimos tienen costo $O(1)$.

Finalmente tenemos que la lista utilizada para los movimientos, \texttt{listaMovimientos}, es una lista doblemente enlazada o \texttt{LinkedList} del tipo
\texttt{Movimiento}. El tipo \texttt{Movimiento} es una clase que simplemente contiene dos \texttt{Posicion}, la posici\'on de la ficha original y la posici\'on
de la ficha despu\'es de realizado el movimiento. Esto implica que una instancia de la Clase \texttt{Movimiento} cuesta $O(1)$ en tiempo y memoria crear.
Adicionalmente, sabemos que la clase \texttt{LinkedList} de Java esta implementada sobre una lista doblemente enlazada, con lo cual la inserci\'on y el
borrado del \'ultimo elementos ambas tienen costo $O(1)$ en tiempo y memoria.

El algoritmo implementado, exceptuando estos detalles, es el mismo que el descripto en secciones anteriores y por lo tanto, al haber adicionalmente
justificado los supuestos presentados en la secci\'on sobre la complejidad de los algoritmos, las demostraciones de correctitud y las cotas de complejidad
prove\'idas son correctas.

\subsection{Resultados}

\subsection{Conclusiones}
